package com.kehao.leetcode.hard.sort_search;

import org.junit.Test;

import java.util.Arrays;

public class WiggleSortSolution {
    public void wiggleSort(int[] nums) {
        middlePick(nums,0,nums.length-1);
        int mid = nums[nums.length/2];
        int low = nums.length/2;
        for (int i = 0; i < low - 1; i++) {
            if(nums[i]==mid){
                while (nums[low]==mid &&low>0) low --;
                if(low>i){
                    int temp = nums[low];
                    nums[low] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        int high = nums.length/2;
        for (int i = nums.length-1; i >high+1; i--) {
            if(nums[i]==mid){
                while (nums[high]==mid&&high<nums.length-1) high ++;
                if(high<i){
                    int temp = nums[high];
                    nums[high] = nums[i];
                    nums[i] = temp;
                }
            }
        }
        int[] copyOf = Arrays.copyOf(nums, nums.length);
        low = (nums.length-1)/2;
        high = nums.length-1;
        for (int i = 0; i < nums.length; i++) {
           nums[i] = i%2==0?copyOf[low--]:copyOf[high--];
        }
    }

    private void middlePick(int[] nums,int start,int end){
        if(start>=end) return;
        int startBegin = start,endBegin = end;
        int temp = nums[start];
        while (start<end){
            while (start<end && nums[end]>temp){
                end --;
            }
            nums[start] = nums[end];
            while (start<end && nums[start]<=temp){
                start++;
            }
            if(start<end){
                nums[end] = nums[start];
            }

        }
        nums[start] = temp;
        if(start<nums.length/2){
            middlePick(nums,start+1,endBegin);
        }else if(start>nums.length/2){
            middlePick(nums,startBegin,start-1);
        }
    }


    @Test
    public void test01(){
        int[] nums = {1,5,1,1,6,4};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test02(){
        int[] nums = {1,3,2,2,3,1};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test03(){
        int[] nums = {5,5,5,4,4,4,4};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test04(){
        int[] nums = {1,1,2,2,2,1};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test05(){
        int[] nums = {1,5,1,1,6,4};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test06(){
        int[] nums = {4,5,5,6};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }

    @Test
    public void test07(){
        int[] nums = {5,3,1,2,6,7,8,5,5};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }
    @Test
    public void test08(){
        int[] nums = {4,5,5,5,5,6,6,6};
        wiggleSort(nums);
        Arrays.stream(nums).forEach(i-> System.out.print(i+" "));
    }
}
